package com.lims.algorithm.algset.graph;

import org.apache.commons.lang3.StringUtils;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * <功能简述>
 *
 * @author lims
 * @date 2020-09-01 14:59
 */
public class UDGraphMatrix<T> {
    /**
     * 最大值
     */
    private static final int INF = Integer.MAX_VALUE;

    /**
     * 顶点集合
     */
    private List<T> vertexs;
    /**
     * 边 矩阵数组（值为权值）
     */
    private int[][] edgeMatrix;
    /**
     * 边数目
     */
    private int edgeNum;
    /**
     * 访问标记
     */
    private boolean[] isVisited;

    public UDGraphMatrix(int n) {
        edgeMatrix = new int[n][n];
        vertexs = new ArrayList<>(n);
        edgeNum = 0;
        isVisited = new boolean[n];
    }

    /**
     * 添加顶点
     */
    public void addVer(T ver) {
        vertexs.add(ver);
    }

    /**
     * 添加边
     */
    public void addEdge(int v1, int v2, int weight) {
        edgeMatrix[v1][v2] = weight;
        edgeMatrix[v2][v1] = weight;
        edgeNum++;
    }

    /**
     * 返回索引的值
     */
    public T getValue(int i) {
        return vertexs.get(i);
    }

    /**
     * 返回v1，v2权重
     */
    public int getWeight(int v1, int v2) {
        return edgeMatrix[v1][v2];
    }

    /**
     * 显示图的矩阵
     */
    public void show() {
        System.out.println("图邻接矩阵显示：");
        for (int[] edge : edgeMatrix) {
            for (int i : edge) {
                System.out.printf("%3d", i);
            }
            System.out.printf("\n");
        }
        System.out.printf("\n");
    }

    /**
     * 得到第一个邻接节点的下标
     */
    public int getFirstAjcVer(int index) {
        for (int j = 0; j < vertexs.size(); j++) {
            // 存在边
            if (edgeMatrix[index][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 根据本节点前一个邻接节点的下标找本节点的下一个邻接节点
     *
     * @return
     */
    public int getNextAjcVer(int v1, int v2) {
        for (int j = v2 + 1; j < vertexs.size(); j++) {
            if (edgeMatrix[v1][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    /**
     * v1下一个未被访问过的邻接点
     */
    public int getNextNoAccessAjcVer(int v1) {
        for (int j = 0; j < vertexs.size(); j++) {
            // 存在边
            if (edgeMatrix[v1][j] > 0 && !isVisited[j]) {
                return j;
            }
        }
        return -1;
    }

    /**
     * 清空访问记录
     */
    public void clearVisited() {
        isVisited = new boolean[vertexs.size()];
    }

    /**
     * 深度优先遍历
     */
    public void DFS() {
        System.out.println("深度优先遍历:");
        List<T> dfsResults = new ArrayList<>();
        for (int i = 0; i < vertexs.size(); i++) {
            if (!isVisited[i]) {
                DFS(isVisited, i, dfsResults);
            }
        }
        System.out.println(StringUtils.join(dfsResults, "->"));
    }

    private void DFS(boolean[] isVisited, int i, List<T> dfsResults) {
        dfsResults.add(getValue(i));
        isVisited[i] = true;
        int ajcVer = getNextNoAccessAjcVer(i);
        while (ajcVer != -1) {
            if (!isVisited[ajcVer]) {
                DFS(isVisited, ajcVer, dfsResults);
            }
            ajcVer = getNextNoAccessAjcVer(ajcVer);
        }
    }

    /**
     * 广度优先遍历
     */
    public void BFS() {
        System.out.println("广度优先遍历:");
        List<T> bfsResults = new ArrayList<>();
        for (int i = 0; i < vertexs.size(); i++) {
            if (!isVisited[i]) {
                BFS(isVisited, i, bfsResults);
            }
        }
        System.out.println(StringUtils.join(bfsResults, "->"));
    }

    private void BFS(boolean[] isVisited, int i, List<T> bfsResults) {
        // 队列头
        int h;
        // 邻接点
        int ajc;
        Queue<Integer> queue = new LinkedBlockingQueue<>();
        bfsResults.add(getValue(i));
        isVisited[i] = true;
        queue.offer(i);
        while (!queue.isEmpty()) {
            // 1.取队列头，未访问邻接点
            h = queue.poll().intValue();
            ajc = getNextNoAccessAjcVer(h);
            while (ajc != -1) {
                // 2.访问邻接点入队列
                if (!isVisited[ajc]) {
                    bfsResults.add(getValue(ajc));
                    isVisited[ajc] = true;
                    queue.offer(ajc);
                }
                // 3.下一个未访问邻接点
                ajc = getNextNoAccessAjcVer(h);
            }
        }
    }

    /**
     * Dijkstra最短路径。(每次确定一个点最短路径后，比较经过此条最短路径到这个点邻接点的路径和原来到邻接点的路径，取最小值)
     * <p>
     * 算法思想：
     * 1.设置两个顶点集S和T，集合S中存放已经找到最短路径的顶点，集合T中存放着当前还未找到最短路径的顶点；
     * 2.初始状态下，集合S中只包含源点V1，T中为除了源点之外的其余顶点，此时源点到各顶点的最短路径为两个顶点所连的边上的权值，
     * ------如果源点V1到该顶点没有边，则最小路径为无穷大；
     * 3.从集合T中选取到源点V1的路径长度最短的顶点Vi加入到集合S中；
     * 4.修改源点V1到集合T中剩余顶点Vj的最短路径长度。
     * ------新的最短路径长度值为Vj原来的最短路径长度值与顶点Vi的最短路径长度加上Vi到Vj的路径长度值中的较小者；
     * 5.不断重复步骤3、4，直至集合T的顶点全部加入到集合S中。
     * <p>
     * <p>
     * 具体步骤：
     * 1.初始化标记数组st[],距离数组distance[]；
     * 2.遍历处理从源到其余顶点的最短路径；
     * 2.1 遍历找到最短路径min和顶点index
     * 2.2 index添加到st[]
     * 2.3 更新distance[]距离数组（index的最短距离确定之后，比较法更新index有出度的邻接点的最短距离）
     * *
     *
     * @param v 单源源点
     * @return 返回值：单源到各点的最短距离数组
     */
    public int[] dijkstra(int v) {
        if (v < 0 || v > vertexs.size()) {
            throw new ArrayIndexOutOfBoundsException();
        }
        // st为标记数组，标记顶点是否已经确定为最短路径了（相当于S集合）
        boolean[] st = new boolean[vertexs.size()];
        // 距离数组
        int[] distance = new int[vertexs.size()];
        // 最短路径中点的前一个点索引
        int[] pre = new int[vertexs.size()];

        // 边矩阵数组
        //int[][] copyEdge = Arrays.copyOfRange(edgeMatrix, 0, edgeMatrix.length);
        int[][] copyEdge = new int[edgeMatrix.length][edgeMatrix.length];
        for (int i = 0; i < edgeMatrix.length; ++i) {
            copyEdge[i] = Arrays.copyOfRange(edgeMatrix[i], 0, edgeMatrix[i].length);
        }

        // 正无穷距离的点
        for (int i = 0; i < vertexs.size(); i++) {
            for (int j = i + 1; j < vertexs.size(); j++) {
                if (copyEdge[i][j] == 0) {
                    copyEdge[i][j] = INF;
                    copyEdge[j][i] = INF;
                }
            }
        }
        // 1.初始化距离
        for (int i = 0; i < vertexs.size(); i++) {
            distance[i] = copyEdge[v][i];
        }
        // 初始化标记st
        st[v] = true;

        // 2.从源到j的路径
        for (int i = 0; i < vertexs.size(); ++i) {
            int min = INF;
            int index = -1;
            // 2.1找min index 比较源到其余结点的路径长度
            for (int j = 0; j < vertexs.size(); ++j) {
                // j最短路径没有确定 找出distance[]中最小路径
                if (st[j] == false) {
                    if (distance[j] < min) {
                        min = distance[j];
                        index = j;
                    }
                }
            }

            // 2.2 更新st[] distance[]
            if (index != -1) {
                st[index] = true;
            }
            for (int j = 0; j < vertexs.size(); ++j) {
                if (st[j] == false) {
                    // 确定的点index和领接点有通路，并比较经过index到达邻接点的路径和原来到达邻接点的路径
                    if (copyEdge[index][j] != INF
                            && min + copyEdge[index][j] < distance[j]) {
                        // 更新距离(<源点O,index,j>距离比<O,j>距离短)
                        distance[j] = min + copyEdge[index][j];
                    }
                }
            }
        }
        System.out.printf("最短路径(源点%d)：\n%s\n", v, Arrays.toString(distance));
        return distance;
    }

    /***********************************************************/
    public static void main(String[] args) {
        // 节点个数
        int n = 7;
        String[] vertexString = {"A", "B", "C", "D", "E", "F", "G"};
        UDGraphMatrix<String> udgMatrix = new UDGraphMatrix<>(n);
        // 向图对象添加节点
        for (String s : vertexString) {
            udgMatrix.addVer(s);
        }

        /**
         * *  /----(12)----B------(10)------C-----\
         * *  |            |               / \    |
         * *  |           (7)             /  |   (3)
         * *  |            |/-----(6)----/   |    |
         * *  A----(16)----F                (5)   D
         * *  |            |\_____(2)_____   |    |
         * *  |           (9)             \  |   (4)
         * *  |            |               \ |    |
         * *  \____(14)____G______(8)________E____/
         * *
         */

        // <A,B> <A,F> <A,G> <B,C> <B,F> <C,D> <C,E> <C,F> <D,E> <E,F> <E,G> <F,G>
        udgMatrix.addEdge(0, 1, 12);
        udgMatrix.addEdge(0, 5, 16);
        udgMatrix.addEdge(0, 6, 14);
        udgMatrix.addEdge(1, 2, 10);
        udgMatrix.addEdge(1, 5, 7);
        udgMatrix.addEdge(2, 3, 3);
        udgMatrix.addEdge(2, 4, 5);
        udgMatrix.addEdge(2, 5, 6);
        udgMatrix.addEdge(3, 4, 4);
        udgMatrix.addEdge(4, 5, 2);
        udgMatrix.addEdge(4, 6, 8);
        udgMatrix.addEdge(5, 6, 9);

        udgMatrix.show();
        udgMatrix.DFS();
        udgMatrix.clearVisited();
        udgMatrix.BFS();

        udgMatrix.dijkstra(3);

        udgMatrix.show();
    }
}
